Cutting a cake, dividing up the property in an estate, determining the borders in an international dispute - such problems of fair division are ubiquitous. Fair Division treats all these problems and many more through a rigorous analysis of a variety of procedures for allocating goods, or deciding who wins on what issues, when there are disputes. Starting with an analysis of the well-known cake-cutting procedure, 'I cut, you choose', the authors show how it has been adapted in a number (...) of fields and then analyze fair-division procedures applicable to situations in which there are more than two parties, or there is more than one good to be divided. In particular they focus on procedures which provide 'envy-free' allocations, in which everybody thinks he or she has received the largest portion and hence does not envy anybody else. They also discuss the fairness of different auction and election procedures. (shrink)

This paper analyzes criteria of fair division of a set of indivisible items among people whose revealed preferences are limited to rankings of the items and for whom no side payments are allowed. The criteria include refinements of Pareto optimality and envy-freeness as well as dominance-freeness, evenness of shares, and two criteria based on equally-spaced surrogate utilities, referred to as maxsum and equimax. Maxsum maximizes a measure of aggregate utility or welfare, whereas equimax lexicographically maximizes persons' utilities from smallest to (...) largest. The paper analyzes conflicts among the criteria along with possibilities and pitfalls of achieving fair division in a variety of circumstances. (shrink)

The concepts of omniscience and omnipotence are defined in 2 ? 2 ordinal games, and implications for the optimal play of these games, when one player is omniscient or omnipotent and the other player is aware of his omniscience or omnipotence, are derived. Intuitively, omniscience allows a player to predict the strategy choice of an opponent in advance of play, and omnipotence allows a player, after initial strategy choices are made, to continue to move after the other player is forced (...) to stop. Omniscience and its awareness by an opponent may hurt both players, but this problem can always be rectified if the other player is omniscient. This pathology can also be rectified if at least one of the two players is omnipotent, which can override the effects of omniscience. In some games, one player's omnipotence ? versus the other's ? helps him, whereas in other games the outcome induced does not depend on which player is omnipotent. Deducing whether a player is superior (omniscient or omnipotent) from the nature of his game playing alone raises several problems, however, suggesting the difficulty of devising tests for detecting superior ability in games. (shrink)

Suppose two players wish to divide a finite set of indivisible items, over which each distributes a specified number of points. Assuming the utility of a player’s bundle is the sum of the points it assigns to the items it contains, we analyze what divisions are fair. We show that if there is an envy-free (EF) allocation of the items, two other desirable properties—Pareto-optimality (PO) and Maximinality (MM)—can also be satisfied, rendering these three properties compatible. But there may be no (...) EF division, in which case some division must satisfy a modification of Bentham’s (1789/2017) “greatest satisfaction of the greatest number” property, called maximum Nash welfare (MNW), that satisfies PO. However, an MNF division may be neither MM nor EFX, which is a weaker form of EF. We conjecture that there is always an EFX allocation that satisfies MM, ensuring that an allocation is maximin, precisely the property that Rawls (1971/1999) championed. We discuss four broader philosophical implications of our more technical analysis. (shrink)

A cornerstone of game theory is backward induction, whereby players reason backward from the end of a game in extensive form to the beginning in order to determine what choices are rational at each stage of play. Truels, or three-person duels, are used to illustrate how the outcome can depend on (1) the evenness/oddness of the number of rounds (the parity problem) and (2) uncertainty about the endpoint of the game (the uncertainty problem). Since there is no known endpoint in (...) the latter case, an extension of the idea of backward induction is used to determine the possible outcomes. The parity problem highlights the lack of robustness of backward induction, but it poses no conflict between foundational principles. On the other hand, two conflicting views of the future underlie the uncertainty problem, depending on whether the number of rounds is bounded (the players invariably shoot from the start) or unbounded (they may all cooperate and never shoot, despite the fact that the truel will end with certainty and therefore be effectively bounded). Some real-life examples, in which destructive behavior sometimes occurred and sometimes did not, are used to illustrate these differences, and some ethical implications of the analysis are discussed. (shrink)

Deterrence means threatening to retaliate against an attack in order to deter it in the first place. The central problem with a policy of deterrence is that the threat of retaliation may not be credible if retaliation leads to a worse outcome - perhaps a nuclear holocaust - than a side would suffer from absorbing a limited first strike and not retaliating. - The optimality of deterrence is analyzed by means of a Deterrence Game based on Chicken, in which each (...) player chooses a probability (or level) of preemption, and of retaliation if preempted. The Nash equilibria, or stable outcomes, in this game are compared with those in a Star Wars Game, in which the preemption and retaliation levels are constrained by the defensive capabilities of each side. Unlike threats in the Deterrence Game, which can always stabilize the cooperative outcome, mutual preemption emerges as an equilibrium in the Star Wars Game, underscoring the problem - particularly if defensive capabilities are unbalanced - that deterrence will be subverted by the development of Star Wars. (shrink)

Issues that arise in using game theory to model national security problems are discussed, including positing nation-states as players, assuming that their decision makers act rationally and possess complete information, and modeling certain conflicts as two-person games. A generic two-person game called the Conflict Game, which captures strategic features of such variable-sum games as Chicken and Prisoners'' Dilemma, is then analyzed. Unlike these classical games, however, the Conflict Game is a two-stage game in which each player can threaten to retaliate (...) — and carry out this threat in the second stage — if its opponent chose noncooperation in the first stage.Conditions for the existence of different pure-strategy Nash equilibria, or stable outcomes, are found, and these results are extended to situations in which the players can select mixed strategies (i.e., make probabilistic threats or choices). Although the Conflict Game sheds light on the rational foundations underlying arms races, nuclear deterrence, and other strategic situations, more detailed assumptions are required to tie this generic game to specific conflicts. (shrink)

1. Introduction The policy of deterrence, at least to avert nuclear war between the superpowers, has been a controversial one. The main controversy arises from the threat of each side to visit destruction on the other in response to an initial attack. This threat would seem irrational if carrying it out would lead to a nuclear holocaust – the worst outcome for both sides. Instead, it would seem better for the side attacked to suffer some destruction rather than to retaliate (...) in kind and, in the process of devastating the other side, seal its own doom in an all-out nuclear exchange. Yet, the superpowers persist in their adherence to deterrence, by which we mean a policy of threatening to retaliate to an attack by the other side in order to deter such an attack in the first place. To be sure, nuclear doctrine for implementing deterrence has evolved over the years, with such appellations as “massive retaliation,” “flexible response,” “mutual assured destruction”, and “counterforce” giving some flavor of the changes in United States strategic thinking. All such doctrines, however, entail some kind of response to a Soviet nuclear attack. They are operationalized in terms of preselected targets to be hit, depending on the perceived nature and magnitude of the attack. Thus, whether U.S. strategic policy at any time stresses a retaliatory attack on cities and industrial centers or on weapons systems and armed forces, the certainty of a response of some kind to an attack is not the issue. (shrink)

It is well known that Nash equilibria may not be Pareto-optimal; worse, a unique Nash equilibrium may be Pareto-dominated, as in Prisoners’ Dilemma. By contrast, we prove a previously conjectured result: every finite normal-form game of complete information and common knowledge has at least one Pareto-optimal nonmyopic equilibrium (NME) in pure strategies, which we define and illustrate. The outcome it gives, which depends on where play starts, may or may not coincide with that given by a Nash equilibrium. We use (...) some simple examples to illustrate properties of NMEs—for instance, that NME outcomes are usually, though not always, maximin—and seem likely to foster cooperation in many games. Other approaches for analyzing farsighted strategic behavior in games are compared with the NME analysis. (shrink)

The Belief Game is a two-person, nonzero-sum game in which both players can do well [e.g., at (3, 4)] or badly [e.g., at (1,1)] simultaneously. The problem that occurs in the play of this game is that its rational outcome of (2, 3) is not only unappealing to both players, especially God, but also, paradoxically, there is an outcome, (3, 4), preferred by both players that is unattainable. Moreover, because God has a dominant strategy, His omniscience does not remedy the (...) situation, though - less plausibly - if man possessed this quality, and God were aware of it, (3, 4) would be attainable.How reasonable is it to use the device of a simple game to argue that nonrevelation by God, and nonbelief by man, are rational strategies? Like any model of a complex reality, the Belief Game abstracts a great deal from the problem that confronts the thoughtful agnostic asking the most profound of existential questions. Yet, to the degree that belief in God is seen as a personal question, conceptualized in terms of a possible relationship one might have with one's Creator, it seems appropriate to try to model this relationship as a game. The most difficult question to answer, I suppose, is, if God exists, what are His preferences in such a game?I have argued that He would first like to be believed, but at the same time not reveal Himself. These goals, in my opinion, are consistent with the role He assumes in many biblical stories, although this is not to say that the Bible offers the final word on philosophical and theological matters in the modern world. Nevertheless, it seems to me to be a logical place from which to start, and the clues it offers on God's preferences seem not contradicted by contemporary events.Of course, the Belief Game supposes that God not only has preferences but makes choices as well. To many people today - myself included - these choices are not apparent. But if He does make them, and in particular chooses not to reveal Himself, I think the Belief Game helps us to understand why nonrevelation is rational. Furthermore, it gives us insight into why, given this choice by God, our own reasons for believing in Him - in a game-theoretic context - may be rendered tenuous. (shrink)

This article examines deception possibilities for two players in simple three-person voting games. An example of one game vulnerable to (tacit) deception by two players is given and its implications discussed. The most unexpected findings of this study is that in those games vulnerable to deception by two players, the optimal strategy of one of them is always to announce his (true) preference order. Moreover, since the player whose optimal announcement is his true one is unable to induce a better (...) outcome for himself by misrepresenting his preference, while his partner can, this player will find that possessing a monopoly of information will not give him any special advantage. In fact, this analysis demonstrates that he may have incentives to share his information selectively with one or another of his opponents should he alone possess complete information at the outset. (shrink)